package video.simple100;

import org.junit.Test;

/**
 * 70. 爬楼梯
 */
public class LeetCode70 {

    @Test
    public void test() {
        int x = 1;
        System.out.println(climbStairs(x));

    }

    //  1、2、3、5、8、13、21、34、55、89......

    /**
     *  1     1
     *  2     2  (1+1  2)
     *  3     3  (1+1+1 1+2  2+1 )
     *  4     5  (1+1+1+1 1+2+1  2+1+1 1+1+2  2+2)
     *  5     8  (1+1+1+1+1 2+1+1+1  2+2+1  2+1+2  1+2+2  1+1+1+2   1+1+2+1  1+2+1+1 )
     *  // 1、2、3、5、8、13、21、34、55、89......
     *   3 = 1+ 2
     *   5 = 3+2
     *   8 = 5+3
     *  13 = 8+5
     */
    public int climbStairs(int n) {
        int x = 1;  // 2  3  5
        int y = 2;  // 3  5  8
        int r = n;
        for (int i = y; i < n; i++) {
            r = x + y;
            x = y;
            y = r;
        }
        return r;
    }
}
